package Leetcode.数组字符串;

/**
 * @Author kirito
 * @Date 2023/12/19 15:43
 * @PackageName:Leetcode.数组字符串
 * @ClassName: 寻找峰值2
 * @Description:
 * 一个 2D 网格中的 峰值 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。
 *
 * 给你一个 从 0 开始编号 的 m x n 矩阵 mat ，其中任意两个相邻格子的值都 不相同 。找出 任意一个 峰值 mat[i][j] 并 返回其位置 [i,j] 。
 *
 * 你可以假设整个矩阵周边环绕着一圈值为 -1 的格子。
 *
 * 要求必须写出时间复杂度为 O(m log(n)) 或 O(n log(m)) 的算法
 *
 * 相比寻找峰值来说其实感觉思路就可以看作是先找行的峰值（一行满足才可能列满足）
 * 然后在满足行的条件下再去找列的峰值，即可找到题意所求的值
 * @Version 1.0
 */
public class 寻找峰值2 {
    public int[] findPeakGrid(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int low = 0, high = m - 1;
        while (low <= high) {
            int i = (low + high) / 2;
            int j = -1, maxElement = -1;
            for (int k = 0; k < n; k++) {
                if (mat[i][k] > maxElement) {
                    j = k;
                    maxElement = mat[i][k];
                }
            }
            if (i - 1 >= 0 && mat[i][j] < mat[i - 1][j]) {
                high = i - 1;
                continue;
            }
            if (i + 1 < m && mat[i][j] < mat[i + 1][j]) {
                low = i + 1;
                continue;
            }
            return new int[]{i, j};
        }
        return new int[0]; // impossible
//        for (int i = 1; i < m-1; i++) {
//            int l = 0, r = n - 1;
//            while (l < r) {
//                int mid = l + (r - l) / 2;
//                if (mat[i][mid] > mat[i][mid + 1]) {
//                    r = mid;
//                }else{
//                    l = mid + 1;
//                }
//            }
//            if (mat[i][r] < mat[i + 1][r] && mat[i][r] > mat[i - 1][r]) {
//                return mat[i];
//            }
//        }
        //怎么确定是哪一行呢？
        ///感觉不应该是这么写，因为没有判断行与行之间的大小关系
    }
}
